①[POJ 2975] Nim
原题链接:http://poj.org/problem?id=2975
题目大意:给定一个个石子,每次可以取个石子的游戏。问先手必胜的操作方案有几种。
数据范围:
多组测试数据
样例输入:
3
7 11 13
2
1000000000 1000000000
0
样例输出:
3
0
首先,如果异或和为显然答案为0。
其次考虑有多少种方案使得初始状态能走到一个必败态:
即对于每一个来说,是否能移动若干个他里面的石子导致异或值到。记异或和为,显然非,对于当前的某一个来说其他的异或和为,若加上了与的异或和变成了,则需要满足除去他之外的异或和是大于他的,即,当满足了这个条件之后,存在从里移动若干个石块使得他的数量变成,使异或和变成0。
因此答案就是满足的数的个数。
②[POJ 3537]Crosses andCrosses
题目大意:有一个的长条格子纸,每次可以往上画一个,最先连出三个的胜利。问是否先手必胜。
注意:原题面虽然没说,但是实际上本题是有多组测试数据的。
数据范围:
多组测试数据
样例输入:
3
6
样例输出:
1
2
可以发现,如果往某一个位置上填了,那么可以等价于前后两个连续的格子都不能放了,于是就可以把这个问题转换成多个有向图游戏的和。记忆化搜索分隔两边分别求救可以了。
不过这个题的效率会非常垃圾。用数组+。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2005;
int f[N],n;
int sg(int n)
{
if(n <= 0) return 0;
if(f[n] != -1) return f[n];
bool st[n + 2];
memset(st,0,sizeof st);
for(int i = 1;i <= n;++i)
st[sg(i - 3) ^ sg(n - i - 2)] = 1;
int res = 0;
while(st[res]) ++res;
return f[n] = res;
}
int main(){
memset(f,-1,sizeof f);
while(~scanf("%d",&n))
puts(sg(n)?"1":"2");
return 0;
}
③[Codeforces 138D]World of Darkraft
题目大意:有一的格子纸,上面写有三种字符。每次可以选一个字符删去它的同时,如果是则删去左下右上的所有格子,如果是则删去右下左上的所有格子,如果是则同时视作和。问是否先手必胜。
数据范围:
样例输入:
2 2
RL
LR
2 2
RR
RR
样例输出:
LOSE
WIN
对角线上的操作难以分割状态,可以把整个棋局旋转,实际的坐标变换就是:,映射结束之后,新的图上就是横向切一刀,就是纵向切一刀。同时整个棋局是可以二染色的,对于二染色之后的图来说,上面的不同颜色的点之间的状态是可以忽视的。因此可以分别求解。
在新图上,对应的坐标范围在到之间。标记当前是找黑色的状态还是白色的状态,分别求出两个值,两者由于独立,异或和大于就先手必胜。
关于这个题为什么入口的坐标可以取整个范围,我个人的理解是这个坐标只是一个范围,标记了整个图上的状态范围。可能这个范围偏大,但是不合法的坐标也不会计入。把范围放大一点可以避免有坐标没算进去。但是这个做法是有一点神棍元素,暂时没想到更好的精确的方法,如果想到了再更新内容。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50;
char g[N][N];
int f[N][N][N][N][2];
int n,m;
int sg(int x1,int y1,int x2,int y2,int flag)
{
if(x1 > x2 || y1 > y2) return 0;
if(f[x1][y1][x2][y2][flag] != -1) return f[x1][y1][x2][y2][flag];
bool st[400];
memset(st,0,sizeof st);
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
int x = i + j,y = i - j + m;
if((i + j & 1) == flag || x1 > x || x > x2 || y1 > y || y > y2) continue;
if(g[i][j] == 'L') st[sg(x + 1,y1,x2,y2,flag) ^ sg(x1,y1,x - 1,y2,flag)] = 1;
if(g[i][j] == 'R') st[sg(x1,y + 1,x2,y2,flag) ^ sg(x1,y1,x2,y - 1,flag)] = 1;
if(g[i][j] == 'X') st[sg(x + 1,y + 1,x2,y2,flag) ^ sg(x1,y1,x - 1,y - 1,flag) ^ sg(x + 1,y1,x2,y - 1,flag) ^ sg(x1,y + 1,x - 1,y2,flag)] = 1;
}
}
int res = 0;
while(st[res]) ++res;
return f[x1][y1][x2][y2][flag] = res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,-1,sizeof f);
for(int i = 1;i <= n;++i) scanf("%s",g[i] + 1);
if(sg(0,0,n + m,n + m,1) ^ sg(0,0,n + m,n + m,0)) puts("WIN");
else puts("LOSE");
return 0;
}